#include <iostream>
#include<queue>

using namespace std;

typedef struct TreeNode
{
    int value;
    struct TreeNode* lChild;
    struct TreeNode* rChild;
    int height;
}TreeNode;

class balancedBinaryTree
{
    public:
        balancedBinaryTree()
        {
            this->root=NULL;
        }
        balancedBinaryTree(int arr[],int length);
        void getHeight(TreeNode* node);
        int max(int,int);

        void levelSearchGetHeight(TreeNode*);
        
        TreeNode* leftChange(TreeNode*);
        TreeNode* rightChange(TreeNode*);
        int helpGetHeight(TreeNode* node);
        int getBalancedFactor(TreeNode* node);
        TreeNode* getMaxNode(TreeNode* node);
        
        TreeNode* reNewNode(int);
        TreeNode* insertNode(TreeNode*,int);
        TreeNode* deleteNode(TreeNode*,int);

        void levelShow();
        void inOrderShow(TreeNode*);

        TreeNode *getRoot()
        {
            return this->root;
        }
        void setRoot(TreeNode* node)
        {
            this->root=node;
        }
    private:
        TreeNode *root;
        TreeNode* helpBuildTree(TreeNode* node,int value);

};

TreeNode* balancedBinaryTree::reNewNode(int value)
{
    TreeNode* tempNode=new TreeNode;
    tempNode->value=value;
    tempNode->lChild=NULL;
    tempNode->rChild=NULL;

    return tempNode;
}

TreeNode* balancedBinaryTree::helpBuildTree(TreeNode* node,int value)
{
    if(node==NULL)
    {
        node=new TreeNode;
        node->value=value;
        node->lChild=NULL;
        node->rChild=NULL;

    }
    else if(node->value<value)
    {
        node->rChild=this->helpBuildTree(node->rChild,value);
    }
    else
    {
        node->lChild=this->helpBuildTree(node->lChild,value);
    }
        return node;
}


balancedBinaryTree::balancedBinaryTree(int arr[],int arrLength)
{
    this->root=new TreeNode;
    this->root->value=arr[0];
    this->root->lChild=NULL;
    this->root->rChild=NULL;
    for(int i=1;i<arrLength;i++)
    {
        helpBuildTree(this->root,arr[i]);
    }
}

int balancedBinaryTree::max(int a,int b)
{
    if(a>b)
    {
        return a;
    }
    return b;
}

int balancedBinaryTree::helpGetHeight(TreeNode* node)
{
    if(node==NULL)
    {
        return 0;
    }
    return 1+max(helpGetHeight(node->lChild),helpGetHeight(node->rChild));
}

void balancedBinaryTree::getHeight(TreeNode* node)
{
    node->height=max(helpGetHeight(node->lChild),helpGetHeight(node->rChild));
}

void balancedBinaryTree::levelSearchGetHeight(TreeNode* node)
{
    queue<TreeNode*> q;
    q.push(this->root);
    TreeNode* tempNode;
    while(!q.empty())
    {
        tempNode=q.front();
        q.pop();
        this->getHeight(tempNode);
        if(tempNode->lChild!=NULL)
        {
            q.push(tempNode->lChild);
        }
        if(tempNode->rChild!=NULL)
        {
            q.push(tempNode->rChild);
        }
    }
}

// 返回左旋之后的根节点
TreeNode* balancedBinaryTree::leftChange(TreeNode* node)
{
    TreeNode* tempNode1=node->rChild;
    TreeNode* tempNode2=tempNode1->lChild;
    node->rChild=tempNode2;
    tempNode1->lChild=node;

    return tempNode1;
}

// 返回右旋之后的根节点
TreeNode* balancedBinaryTree::rightChange(TreeNode* node)
{
    TreeNode* tempNode1=node->lChild;
    TreeNode* tempNode2=tempNode1->rChild;
    node->lChild=tempNode2;
    tempNode1->rChild=node;

    return tempNode1;
}

int balancedBinaryTree::getBalancedFactor(TreeNode* node)
{
    if(node==NULL)
    {
        return 0;
    }
    this->levelSearchGetHeight(this->root);
    return helpGetHeight(node->lChild)-helpGetHeight(node->rChild);
}

TreeNode* balancedBinaryTree::insertNode(TreeNode* node,int value)
{
    if(node==NULL)
    {
        node=reNewNode(value);
        return node;
    }
    else if(node->value<value)
    {
        node->rChild=this->insertNode(node->rChild,value);
    }
    else
    {
        node->lChild=this->insertNode(node->lChild,value);
    }

    int bf=this->getBalancedFactor(node);

    // LL型不平衡,需要右旋
    if(bf>1 && value<node->value)
    {
        return this->rightChange(node);
    }

    // RR型不平衡，需要左旋
    else if(bf<-1 && value>node->value)
    {
        return this->leftChange(node);
    }

    // LR型不平衡，先左旋再右旋
    else if(bf>1 && value>node->value)
    {
        node->lChild=this->leftChange(node->lChild);
        return this->rightChange(node);
    }

    // RL型不平衡，先右旋再左旋
    else if(bf<-1 && value<node->value)
    {
        node->rChild=this->rightChange(node->rChild);
        return this->leftChange(node->lChild);
    }

    return node;
}

TreeNode* balancedBinaryTree::getMaxNode(TreeNode* node)
{
    TreeNode* tempNode=node->rChild;
    while(tempNode->lChild!=NULL)
    {
        tempNode=tempNode->lChild;
    }
    return tempNode;
}

TreeNode* balancedBinaryTree::deleteNode(TreeNode* node,int value)
{
    if(node==NULL)
    {
        return node;
    }
    if(node->value<value)
    {
        node->rChild=this->deleteNode(node->rChild,value);
    }
    else if(node->value>value)
    {
        node->lChild=this->deleteNode(node->lChild,value);
    }
    else
    {
        // 叶子结点
        if(node->lChild==NULL && node->rChild==NULL)
        {
            delete node;
            return NULL;
        }
        // 度为一的结点
        else if(node->lChild==NULL)
        {
            TreeNode* tempNode;
            tempNode=node->rChild;
            delete node;
            node=tempNode;
        }
        // 度为一的结点
        else if(node->rChild==NULL)
        {
            TreeNode* tempNode;
            tempNode=node->lChild;
            delete node;
            node=tempNode;
        }
        // 左右子树都不为空的结点
        else
        {
            TreeNode* tempNode=getMaxNode(node);
            node->value=tempNode->value;
            deleteNode(node->rChild,tempNode->value);
        }
    }

    int bf=this->getBalancedFactor(node);

    // LL型不平衡,需要右旋
    if(bf>1 && value<node->value)
    {
        return this->rightChange(node);
    }

    // RR型不平衡，需要左旋
    else if(bf<-1 && value>node->value)
    {
        return this->leftChange(node);
    }

    // LR型不平衡，先左旋再右旋
    else if(bf>1 && value>node->value)
    {
        node->lChild=this->leftChange(node->lChild);
        return this->rightChange(node);
    }

    // RL型不平衡，先右旋再左旋
    else if(bf<-1 && value<node->value)
    {
        node->rChild=this->rightChange(node->rChild);
        return this->leftChange(node->lChild);
    }


    return node;
}

void balancedBinaryTree::levelShow()
{
    queue<TreeNode*> q;
    TreeNode* tempNode;
    q.push(this->root);
    while(!q.empty())
    {
        tempNode=q.front();
        q.pop();
        cout<<tempNode->value<<' ';
        if(tempNode->lChild!=NULL)
        {
            q.push(tempNode->lChild);
        }
        if(tempNode->rChild!=NULL)
        {
            q.push(tempNode->rChild);
        }
    }
}

void balancedBinaryTree::inOrderShow(TreeNode* node)
{
    if(node->lChild!=NULL)
    {
        this->inOrderShow(node->lChild);
    }
    cout<<node->value<<' ';
    if(node->rChild!=NULL)
    {
        this->inOrderShow(node->rChild);
    }    
}

int main()
{       
    int arr[8]={90,12,14,1,4,46,32,6};
    balancedBinaryTree tree(arr,8);
    tree.getHeight(tree.getRoot());
    cout<<tree.getRoot()->height<<endl;
    tree.levelSearchGetHeight(tree.getRoot());
    cout<<tree.getRoot()->lChild->lChild->rChild->height<<endl;

    balancedBinaryTree tree2;
    for(int i=0;i<8;i++)
    {
        tree2.setRoot(tree2.insertNode(tree2.getRoot(),arr[i]));
    }

    cout<<"--------------"<<endl;
    tree2.levelShow();
    cout<<"\n----------------------"<<endl;
    tree2.inOrderShow(tree2.getRoot());
    tree2.setRoot(tree2.insertNode(tree2.getRoot(),98));
    tree2.setRoot(tree2.insertNode(tree2.getRoot(),43));
    cout<<'\n'<<"---------------"<<endl;
    tree2.inOrderShow(tree2.getRoot());
    tree2.deleteNode(tree2.getRoot(),43);
    cout<<'\n'<<"---------------"<<endl;
    tree2.inOrderShow(tree2.getRoot());
    tree2.deleteNode(tree2.getRoot(),6);
    cout<<'\n'<<"---------------"<<endl;
    tree2.inOrderShow(tree2.getRoot());
}